The invention relates to a method of tracking down a prespecified subcircuit in an electrical circuit equivalent, the subcircuit being prespecified by a template circuit comprising a pattern of interconnections between interconnected template elements in the template circuit and associated type conditions for each interconnected template element.
The invention also relates to a method of constructing processing masks for fabrication of an integrated semiconductor circuit, in which a chain of descriptions of an electrical circuit is generated,
starting with an initial description in terms of elements and their connections, PA1 proceeding with successors in said chain, generated by successive replacement of the elements by subcircuits for implementing the respective functions of the elements, and PA1 ending with a layout description generated for the processing masks, under control of which patterns are applied to the processing masks for implementing said functions in the integrated circuit, the method comprising a feedback step for checking said successive replacement, and on the basis of this checking correcting the replacement if necessary, the feedback step comprising PA1 starting from an intermediate description from said chain, PA1 generating a reconstructed description by substituting effective elements for occurrences of a subcircuit matching a template for the implementation of the effective element, PA1 performing said checking by comparing the reconstructed description with a predecessor description, which precedes the intermediate description in the sequence. PA1 element C1: two input AND gate PA1 element C2 and C3: a first and second inverter, PA1 element N1: node connected at least to input of AND gate, PA1 element N2: node connected to output of AND gate and input of inverter, PA1 element N3: output node connected to output of inverter, input of inverter and input of AND gate PA1 element N4: node connected at least to output of inverter, The connection conditions require connections PA1 from N1 to an input of C1, PA1 from the output of C1 to N2, PA1 from N2 to the input of C2, PA1 from the output of C2 to N3, PA1 from N3 to an input of C1, PA1 from N3 to the input of C3, PA1 from the output of C3 to N4, PA1 counting, for each particular associated type condition, a respective occurrence rate of circuit elements in the electrical circuit equivalent which meet the type condition, PA1 selecting an initial template element whose type condition corresponds to a lowest occurrence rate, PA1 selecting an initial circuit element meeting the type condition for the initial template element, PA1 searching, in the electrical circuit equivalent, for successive further circuit elements, interconnected to the initial circuit element according to the pattern and satisfying the type conditions for the template elements, until either all template elements are identified or persistent failure is met.
The invention also relates to a device for tracking down a prespecified subcircuit in an electrical circuit equivalent, the subcircuit being prespecified by a pattern of interconnections between interconnected template elements and respective type conditions for the interconnected template elements.
Such methods and such a device are known from a publication titled "Automatic verification of library based IC designs" by T. Kostelijk and B. de Loore in the IEEE journal of solid state circuits vol. 26. No. 3, mar. 1991, pages 394 to 403.
Electrical circuits are usually combinations of subcircuits. For example, processor circuits comprise subcircuits like memory cells, adder circuits, multiplexing circuits, logic gates etcetera; radio receiving circuits may comprise amplifier stages, oscillator circuits, mixing circuits, filter circuits, etcetera.
For a number of applications, it is necessary to make automated comparisons between electrical circuits and template circuits. In the process which results in an integrated circuit, for example, there is a chain of many intermediate products, such as system level circuit descriptions, gate level circuit descriptions, transistor level circuit descriptions, layout descriptions, masks etc. which eventually lead to finished chips. The intermediate products in the chain are produced by devices that may produce errors, for example when they require human intervention. Most of todays chips are so complex that it is practically impossible to guarantee that these devices, unchecked, will produce no such errors. Instead, the devices are provided with a feedback mechanism, which matches intermediate products to predecessors in the chain, in order to localize any errors and correct them. To be able to check any intermediate products even when they occur in the context of a larger circuit, it is necessary to detect subcircuits in this larger circuit. Other applications of subcircuit detection include, for example, automated diagnosis and repair of faulty circuits, or detection of subcircuits that infringe some patent.
According to the abovementioned publication, a template provides specifications of subcircuits which must be tracked down in the electrical circuit, or any description equivalent to it. If one of its subcircuits is to meet a specification, the electrical circuit equivalent must contain elements that match template elements. The elements include physical components, like for example transistors, resistors, AND gates, registers etcetera. As the word "elements" is intended here, the elements of the template and circuit may also include input terminals, power supply terminals, and in general any interconnection wiring between physical components.
For each template element, the template comprises a type condition, which specifies of what type a circuit element should be to be match the template element (e.g. "P type transistor", "power supply node", "wiring connected to output of AND gate and input of inverter"). In addition, the type condition may also specify a range for the parameters of a circuit element (e.g. "P transistor with width between 10 and 20 micron, and length between 1 and 2 micron", "resistor between 10 and 1000 ohm" etcetera). Moreover, the template comprises a pattern of interconnections between the template elements to which the interconnections in the circuit must correspond if they are to identified as the prespecified subcircuit.
As an example, the type conditions for elements of the template circuit shown in FIG. 1 are
In addition, parameter ranges (like fan-out of C2 between 2 and 3) may be specified for the elements in the type conditions.
According to the above-mentioned publication, when a prespecified subcircuit is tracked down in an electrical circuit equivalent one starts by considering an initial template element (e.g. C1 from FIG. 1) and selects an initial circuit element (e.g. an AND gate) from the electrical circuit, for which it is verified that it matches the type condition for the initial template element. Subsequently, second, third etc. circuit elements are chosen which must correspond to a second, third etc. template element (e.g. C2, C3 etc.). After each selection, it is verified that the selected circuit element meets the type condition for the corresponding template element. For each further selected circuit element after the first circuit element, it is moreover verified that the selected circuit element satisfies the interconnection pattern as far as this pattern concerns earlier selected circuit elements; when a further circuit element falls this verification, one tracks back on the selection of the circuit elements, and tries a new selection until all template components have been identified, which means that the subcircuit has been found.
In principle, many possible combinations of elements of the circuit have to be selected and verified. The problem with this method of tracking down the subcircuit is therefore that, especially when tracking down a subcircuit in a much larger electrical circuit, the risk exists that very many possible combinations of circuit elements need to be searched which do not yield subcircuit detection. Depending on the number of other subcircuits used in the circuit, and particularly those only partially matching the template, this can make the method expensive and slow in terms of computation time required for search with all but the simplest templates and small circuits.